package com.arron.algorithm.leetcodetop100.动态规划;

import java.util.Arrays;

public class 编辑距离 {

    int[][] dp;

    public int minDistance(String word1, String word2) {

        char[] wordChar1 = word1.toCharArray();
        char[] wordChar2 = word2.toCharArray();

        dp = new int[word1.length() + 1][word2.length() + 1];


        for (int[] dps : dp) {
            Arrays.fill(dps, -1);
        }
        return dfs(wordChar1, word1.length() - 1, wordChar2, word2.length() - 1);
    }


    public int dfs(char[] chars1, int i, char[] chars2, int j) {

        if (i < 0) {
            //当一个字符走完了，剩下的需要删除 字符串 j+1个，及删除操作j+1
            return j + 1;
        }

        if (j < 0) {
            return i + 1;
        }

        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        if (chars1[i] == chars2[j]) {
            dp[i][j] = dfs(chars1, i - 1, chars2, j - 1);
        } else {

            dp[i][j] = min(dfs(chars1, i, chars2, j - 1) + 1, /* 在word1中插入s2[j]*/
                    dfs(chars1, i - 1, chars2, j - 1) + 1, /* 在 word1中替换 s1[i] 为s[j]*/
                    dfs(chars1, i - 1, chars2, j) + 1); /*删除s1中的s[i]*/
        }

        return dp[i][j];
    }

    public int minDistance(char[] chars1, char[] chars2) {

        int[][] dp = new int[chars2.length + 1][chars1.length + 1];

        for (int i = 0; i <= chars1.length; i++) {

            dp[0][i] = i;
        }
        for (int i = 0; i <= chars2.length; i++) {
            dp[i][0] = i;

        }


        for (int i = 1; i <= chars2.length; i++) {

            for (int j = 1; j <= chars1.length; j++) {

                if (chars1[j - 1] == chars2[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j -1] + 1);
                }

            }

        }
        return dp[chars2.length][chars1.length];

    }


    public int min(int a, int b, int c) {
        return a > b ? (Math.min(b, c)) : (Math.min(a, c));
    }

    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        编辑距离 distance = new 编辑距离();

        distance.minDistance(word1.toCharArray(),word2.toCharArray());
    }

}
